package com.gjx.leetcode;

import java.util.Arrays;

//43. 字符串相乘
//
//给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
//
//示例 1:
//
//输入: num1 = "2", num2 = "3"
//输出: "6"
//示例 2:
//
//输入: num1 = "123", num2 = "456"
//输出: "56088"
//说明：
//
//num1 和 num2 的长度小于110。
//num1 和 num2 只包含数字 0-9。
//num1 和 num2 均不以零开头，除非是数字 0 本身。
//不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。




public class Solution043 {
	public String multiply(String num1, String num2) {
        
		if (num1.equals("0") || num2.equals("0")) {
			return "0";
		}
		
		char[] res = new char[num1.length() + num2.length()];
		
		for (int i=num2.length()-1; i>=0; i--) {
			for (int j=num1.length()-1; j>=0; j--) {
				res[i+j+1] += (num1.charAt(j) - '0') * (num2.charAt(i) - '0');
			}
			
		}
		
		
		int carry = 0;
		for (int i=res.length-1; i>=0; i--) {
			res[i] += carry;
			carry = res[i] / 10;
			res[i] %= 10;
		}
		
		int beginIndex = 0;
		
		for (int i=0; i<res.length; i++) {
			if (res[i] == 0) {
				beginIndex++;
			} else {
				break;
			}
		}
		
		for (int i=beginIndex; i<res.length; i++) {
			res[i] += '0';
		}
		
		return new String(res, beginIndex, res.length - beginIndex);
		
    }
	
	private String mul(String num, char c) {
		
		int carry = 0;
		
		StringBuilder sb = new StringBuilder();
		
		for (int i=num.length()-1; i>=0; i--) {
			int val = (num.charAt(i) - '0') * (c - '0') + carry;
			sb.append(val % 10);
			carry = val / 10;
		}
		
		if (carry != 0) {
			sb.append(carry);
		}
		return sb.reverse().toString();
	}
	
	private String add(String num1, String num2) {
		int carry = 0;
		
		StringBuilder sb = new StringBuilder();
		
		int i = num1.length()-1; 
		int j = num2.length()-1;
		
		while (i >= 0 || j >= 0) {
			
			int a = 0;
			if (i >= 0) {
				a = num1.charAt(i) - '0';
				i--;
			}
			
			int b = 0;
			if (j >= 0) {
				b = num2.charAt(j) - '0';
				j--;
			}
			
			int val = a + b + carry;
			
			sb.append(val % 10);
			carry = val / 10;
			
		}
		
		if (carry != 0) {
			sb.append(carry);
		}
		
		return sb.reverse().toString();
	}
	
	
	public static void main(String[] args) {
		new Solution043().multiply("123", "23");
	}
}
